package com.yanceysong.codetop.s1_s10;

/**
 * @ClassName S10_Mid_5_最长回文子串
 * @Description
 * @date 2024/8/11 上午12:44
 * @Author yanceysong
 * @Version 1.0
 */
public class S10_Mid_5_最长回文子串 {
    /**
     * LeetCode链接
     * <a href="https://leetcode.cn/problems/longest-palindromic-substring/description/">...</a>
     * <p>
     * 给你一个字符串 s，找到 s 中最长的回文子串。
     * <p>
     * 示例1：
     * 输入：s = "babad"
     * 输出："bab"
     * 解释："aba" 同样是符合题意的答案。
     * <p>
     * 示例2：
     * 输入：s = "cbbd"
     * 输出："bb"
     * <p>
     * 提示：
     * 1 <= s.length <= 1000
     * s 仅由数字和英文字母组成
     * <p>
     * 解题：
     * {@link com.yanceysong.codetop.s1_s10.S10_Mid_5_最长回文子串#longestPalindrome(java.lang.String)}
     * <p>
     * ==================== 最长回文子串算法图解 ====================
     * <p>
     * 算法思路：中心扩散法（Center Expansion）
     * 1. 遍历字符串的每个位置作为回文中心
     * 2. 从中心向两边扩散，检查是否构成回文
     * 3. 处理奇数长度和偶数长度的回文情况
     * 4. 记录最长回文子串的位置和长度
     * <p>
     * 执行示例：s = "babad"
     * <p>
     * 字符串索引：
     * 索引: 0 1 2 3 4
     * 字符: b a b a d
     * <p>
     * 中心扩散过程详解：
     * <p>
     * 第1步：以索引0('b')为中心扩散
     * 初始状态: center=0, left=-1, right=1
     * b a b a d
     * ^
     * center
     * <p>
     * 扩散过程：
     * 1. 处理相同字符：left=0, charArray[0]='b', 无左侧相同字符
     * 2. 处理相同字符：right=0, charArray[0]='b', 无右侧相同字符
     * 3. 向两边扩散：left=-1(越界), right=1, charArray[1]='a' ≠ 'b'
     * 结果：回文长度=1, 回文="b"
     * <p>
     * 第2步：以索引1('a')为中心扩散
     * 初始状态: center=1, left=0, right=2
     * b a b a d
     * ^
     * center
     * <p>
     * 扩散过程：
     * 1. 处理相同字符：left=1, charArray[1]='a', 检查左侧charArray[0]='b' ≠ 'a'
     * 2. 处理相同字符：right=1, charArray[1]='a', 检查右侧charArray[2]='b' ≠ 'a'
     * 3. 向两边扩散：left=0, right=2, charArray[0]='b' == charArray[2]='b' ✓
     * 继续扩散：left=-1(越界), right=3
     * 结果：回文长度=3, 回文="bab"
     * <p>
     * 第3步：以索引2('b')为中心扩散
     * 初始状态: center=2, left=1, right=3
     * b a b a d
     * ^
     * center
     * <p>
     * 扩散过程：
     * 1. 处理相同字符：无左右相同字符
     * 2. 向两边扩散：left=1, right=3, charArray[1]='a' == charArray[3]='a' ✓
     * 继续扩散：left=0, right=4, charArray[0]='b' ≠ charArray[4]='d'
     * 结果：回文长度=3, 回文="aba"
     * <p>
     * 第4步：以索引3('a')为中心扩散
     * 结果：回文长度=1, 回文="a"
     * <p>
     * 第5步：以索引4('d')为中心扩散
     * 结果：回文长度=1, 回文="d"
     * <p>
     * 最终结果：最长回文子串="bab"或"aba"，长度=3
     * <p>
     * ==================== 指针移动原因详解 ====================
     * <p>
     * 中心扩散法的三个阶段及指针移动原因：
     * <p>
     * 阶段1：处理左侧相同字符
     * 目的：处理偶数长度回文的情况，如"aa", "aaa"
     * 移动规则：while(left >= 0 && charArray[left] == charArray[center])
     * 移动原因：
     * - 连续相同的字符本身就构成回文
     * - 需要将所有相同字符包含在回文中心
     * - 为后续的对称扩散做准备
     * <p>
     * 示例："aaa"
     * center=1时：
     * a a a
     * ^
     * center
     * left指针从0开始，charArray[0]='a' == charArray[1]='a'，left左移到-1
     * 结果：将连续的'a'都包含在回文中心
     * <p>
     * 阶段2：处理右侧相同字符
     * 目的：同阶段1，处理右侧的连续相同字符
     * 移动规则：while(right < length && charArray[right] == charArray[center])
     * 移动原因：与阶段1相同，确保连续相同字符都被包含
     * <p>
     * 阶段3：对称扩散
     * 目的：检查回文的对称性，寻找最长回文
     * 移动规则：while(left >= 0 && right < length && charArray[left] == charArray[right])
     * 移动原因：
     * - 回文的定义：从中心向两边，对应位置的字符必须相同
     * - 当两端字符相同时，可以安全地扩展回文边界
     * - 当两端字符不同时，回文扩散结束
     * <p>
     * 示例："babad"中以'a'(索引1)为中心：
     * b a b a d
     * ^ ^ ^
     * L C R
     * charArray[0]='b' == charArray[2]='b' ✓，继续扩散
     * 下一轮：left=-1(越界)，扩散结束
     * <p>
     * 关键优化点：
     * 1. 一次遍历处理奇数和偶数长度回文
     * 2. 通过处理相同字符避免重复计算
     * 3. 边界检查防止数组越界
     * 4. 及时更新最长回文记录
     * <p>
     * 时间复杂度：O(n²)，最坏情况下每个中心需要扩散n次
     * 空间复杂度：O(1)，只使用常数个额外变量
     * <p>
     * ================================================================
     */
    public String longestPalindrome(String s) {
        // 边界检查：空字符串直接返回
        if (s.isEmpty()) {
            return "";
        }

        // 初始化变量
        int strLen = s.length();                    // 字符串长度
        int left, right;                            // 左右扩散指针
        int maxLen = 0;                             // 记录最长回文子串的长度
        int maxStart = 0;                           // 记录最长回文子串的起始位置
        char[] charArray = s.toCharArray();         // 转换为字符数组，提高访问效率

        // 中心扩散法：遍历每个可能的回文中心
        for (int i = 0; i < strLen; i++) {
            // 步骤1：初始化扩散指针
            left = i - 1;                           // 左指针指向中心的左侧
            right = i + 1;                          // 右指针指向中心的右侧
            int len = 1;                            // 当前回文长度，初始为1（包含中心字符）

            // 步骤2：处理左侧连续相同字符（解决偶数长度回文问题）
            // 目的：将所有与中心字符相同的左侧字符纳入回文中心
            // 示例："aaa"中心为索引1时，需要将索引0的'a'也包含进来
            while (left >= 0 && charArray[left] == charArray[i]) {
                left--;                             // 左指针继续左移
                len++;                              // 回文长度增加1
            }

            // 步骤3：处理右侧连续相同字符（解决偶数长度回文问题）
            // 目的：将所有与中心字符相同的右侧字符纳入回文中心
            // 示例："aaa"中心为索引1时，需要将索引2的'a'也包含进来
            while (right < strLen && charArray[right] == charArray[i]) {
                right++;                            // 右指针继续右移
                len++;                              // 回文长度增加1
            }

            // 步骤4：对称扩散检查回文性质
            // 目的：检查回文的对称性，寻找最长的回文子串
            // 条件：两端字符必须相同才能继续扩散
            while (left >= 0 && right < strLen && charArray[left] == charArray[right]) {
                left--;                             // 左指针继续左移
                right++;                            // 右指针继续右移
                len += 2;                           // 回文长度增加2（左右各1个字符）
            }

            // 步骤5：更新最长回文记录
            if (len > maxLen) {
                maxLen = len;                       // 更新最长回文长度
                maxStart = left;                    // 记录起始位置（注意：left已经多减了1）
            }
        }

        // 返回最长回文子串
        // 注意：left指针在最后一次循环中多减了1，所以起始位置是left+1
        return s.substring(maxStart + 1, maxStart + maxLen + 1);
    }

    public static void main(String[] args) {
        S10_Mid_5_最长回文子串 solution = new S10_Mid_5_最长回文子串();

        System.out.println("=== 最长回文子串测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 不同长度回文测试
        System.out.println("\n--- 测试3: 不同长度回文测试 ---");
        testDifferentLengthPalindromes(solution);

        // 测试4: 特殊情况测试
        System.out.println("\n--- 测试4: 特殊情况测试 ---");
        testSpecialCases(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        // 测试6: 复杂回文模式测试
        System.out.println("\n--- 测试6: 复杂回文模式测试 ---");
        testComplexPalindromePatterns(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S10_Mid_5_最长回文子串 solution) {
        // 示例1: "babad" -> "bab" 或 "aba"
        String input1 = "babad";
        String result1 = solution.longestPalindrome(input1);
        System.out.println("输入: \"" + input1 + "\" -> 输出: \"" + result1 + "\" (期望: \"bab\" 或 \"aba\")");
        assert result1.equals("bab") || result1.equals("aba") : "示例1测试失败";

        // 示例2: "cbbd" -> "bb"
        String input2 = "cbbd";
        String expected2 = "bb";
        String result2 = solution.longestPalindrome(input2);
        System.out.println("输入: \"" + input2 + "\" -> 输出: \"" + result2 + "\" (期望: \"" + expected2 + "\")");
        assert result2.equals(expected2) : "示例2测试失败";

        // 示例3: 单字符
        String input3 = "a";
        String expected3 = "a";
        String result3 = solution.longestPalindrome(input3);
        System.out.println("输入: \"" + input3 + "\" -> 输出: \"" + result3 + "\" (期望: \"" + expected3 + "\")");
        assert result3.equals(expected3) : "示例3测试失败";

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S10_Mid_5_最长回文子串 solution) {
        // 测试1: 空字符串
        String input1 = "";
        String expected1 = "";
        String result1 = solution.longestPalindrome(input1);
        System.out.println("空字符串: \"" + input1 + "\" -> \"" + result1 + "\" (期望: \"" + expected1 + "\")");
        assert result1.equals(expected1) : "空字符串测试失败";

        // 测试2: 单字符
        String input2 = "x";
        String expected2 = "x";
        String result2 = solution.longestPalindrome(input2);
        System.out.println("单字符: \"" + input2 + "\" -> \"" + result2 + "\" (期望: \"" + expected2 + "\")");
        assert result2.equals(expected2) : "单字符测试失败";

        // 测试3: 两个相同字符
        String input3 = "aa";
        String expected3 = "aa";
        String result3 = solution.longestPalindrome(input3);
        System.out.println("两个相同字符: \"" + input3 + "\" -> \"" + result3 + "\" (期望: \"" + expected3 + "\")");
        assert result3.equals(expected3) : "两个相同字符测试失败";

        // 测试4: 两个不同字符
        String input4 = "ab";
        String result4 = solution.longestPalindrome(input4);
        System.out.println("两个不同字符: \"" + input4 + "\" -> \"" + result4 + "\" (期望: \"a\" 或 \"b\")");
        assert result4.equals("a") || result4.equals("b") : "两个不同字符测试失败";

        // 测试5: 整个字符串都是回文
        String input5 = "racecar";
        String expected5 = "racecar";
        String result5 = solution.longestPalindrome(input5);
        System.out.println("整个字符串回文: \"" + input5 + "\" -> \"" + result5 + "\" (期望: \"" + expected5 + "\")");
        assert result5.equals(expected5) : "整个字符串回文测试失败";

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 测试不同长度的回文
     */
    private static void testDifferentLengthPalindromes(S10_Mid_5_最长回文子串 solution) {
        // 测试1: 奇数长度回文
        testPalindrome(solution, "abcba", "abcba", "奇数长度回文(5)");
        testPalindrome(solution, "racecar", "racecar", "奇数长度回文(7)");
        testPalindrome(solution, "abcdcba", "abcdcba", "奇数长度回文(7)");

        // 测试2: 偶数长度回文
        testPalindrome(solution, "abba", "abba", "偶数长度回文(4)");
        testPalindrome(solution, "aabbaa", "aabbaa", "偶数长度回文(6)");
        testPalindrome(solution, "abccba", "abccba", "偶数长度回文(6)");

        // 测试3: 混合情况
        testPalindrome(solution, "abcbad", "bcb", "包含奇数回文的字符串");
        testPalindrome(solution, "abccbad", "bccb", "包含偶数回文的字符串");

        System.out.println("✓ 不同长度回文测试通过");
    }

    /**
     * 测试特殊情况
     */
    private static void testSpecialCases(S10_Mid_5_最长回文子串 solution) {
        // 测试1: 全部相同字符
        testPalindrome(solution, "aaaa", "aaaa", "全部相同字符");
        testPalindrome(solution, "bbbbb", "bbbbb", "全部相同字符(5个)");

        // 测试2: 数字字符串
        testPalindrome(solution, "12321", "12321", "数字回文");
        testPalindrome(solution, "123454321", "123454321", "长数字回文");

        // 测试3: 混合字符
        testPalindrome(solution, "a1b2b1a", "a1b2b1a", "数字字母混合回文");
        testPalindrome(solution, "A1a1A", "A1a1A", "大小写数字混合");

        // 测试4: 无回文(除单字符外)
        testPalindrome(solution, "abcdef", "a", "无回文字符串");
        testPalindrome(solution, "abcdefg", "a", "无回文字符串(7个字符)");

        // 测试5: 回文在开头
        testPalindrome(solution, "abbadefg", "abba", "回文在开头(长)");

        // 测试6: 回文在结尾
        testPalindrome(solution, "abcdefgg", "gg", "回文在结尾");
        testPalindrome(solution, "abcdracecar", "racecar", "回文在结尾(长)");

        System.out.println("✓ 特殊情况测试通过");
    }

    /**
     * 辅助方法：测试单个回文用例
     */
    private static void testPalindrome(S10_Mid_5_最长回文子串 solution, String input, String expected, String description) {
        String result = solution.longestPalindrome(input);
        System.out.println(description + " - 输入: \"" + input + "\" -> 输出: \"" + result + "\" (期望: \"" + expected + "\")");
        assert result.equals(expected) : description + "测试失败";
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S10_Mid_5_最长回文子串 solution) {
        // 测试1: 中等长度字符串
        System.out.println("性能测试1: 100个字符");
        testPerformanceCase(solution, 100);

        // 测试2: 较长字符串
        System.out.println("性能测试2: 500个字符");
        testPerformanceCase(solution, 500);

        // 测试3: 长字符串
        System.out.println("性能测试3: 1000个字符");
        testPerformanceCase(solution, 1000);

        System.out.println("✓ 性能测试通过");
    }

    /**
     * 辅助方法：性能测试用例
     */
    private static void testPerformanceCase(S10_Mid_5_最长回文子串 solution, int length) {
        // 创建测试字符串：前半部分 + 回文中心 + 后半部分
        StringBuilder sb = new StringBuilder();

        // 添加前半部分随机字符
        for (int i = 0; i < length / 3; i++) {
            sb.append((char) ('a' + i % 26));
        }

        // 添加回文部分
        String palindrome = "racecar";
        sb.append(palindrome);

        // 添加后半部分随机字符
        for (int i = 0; i < length - length / 3 - palindrome.length(); i++) {
            sb.append((char) ('z' - i % 26));
        }

        String input = sb.toString();

        long startTime = System.currentTimeMillis();
        String result = solution.longestPalindrome(input);
        long endTime = System.currentTimeMillis();

        // 验证结果不为空且是回文
        assert result != null && result.length() > 0 : "性能测试：结果不应为空";
        assert isPalindrome(result) : "性能测试：结果应该是回文";

        System.out.println("  字符串长度: " + input.length() +
                           ", 最长回文长度: " + result.length() +
                           ", 执行时间: " + (endTime - startTime) + "ms");

        // 验证时间复杂度合理
        assert (endTime - startTime) < 1000 : "性能测试：执行时间过长，可能存在性能问题";
    }

    /**
     * 测试复杂回文模式
     */
    private static void testComplexPalindromePatterns(S10_Mid_5_最长回文子串 solution) {
        // 测试1: 嵌套回文
        testPalindrome(solution, "abacabad", "abacaba", "嵌套回文");

        // 测试2: 重叠回文
        testPalindrome(solution, "aabaa", "aabaa", "重叠回文");

        // 测试3: 多个相同长度回文
        String input3 = "abcba12321";
        String result3 = solution.longestPalindrome(input3);
        System.out.println("多个相同长度回文 - 输入: \"" + input3 + "\" -> 输出: \"" + result3 + "\" (期望: \"abcba\" 或 \"12321\")");
        assert result3.equals("abcba") || result3.equals("12321") : "多个相同长度回文测试失败";

        // 测试4: 连续相同字符中的回文
        testPalindrome(solution, "aaabaaaa", "aaabaaaa", "连续相同字符中的回文");

        // 测试5: 复杂混合模式
        testPalindrome(solution, "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz", "a", "无明显回文的长字符串");

        System.out.println("✓ 复杂回文模式测试通过");
    }

    /**
     * 辅助方法：验证字符串是否为回文
     */
    private static boolean isPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return true;
        }

        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }
}
